콜 스택

3. 기능

콜 스택은 스택 자료구조를 기반으로 동작하며, 함수 호출 시 반환 주소, 지역 변수, 매개변수 등을 저장하는 데 사용된다. 함수가 호출되면 해당 함수의 정보(반환 주소, 지역 변수 등)가 콜 스택에 푸시되고, 함수 실행이 완료되면 해당 정보가 팝되어 이전 상태로 복귀한다. 이러한 과정을 통해 프로그램의 실행 흐름을 제어하고 함수 간의 관계를 관리한다.^[7]

일반적으로 실행 중인 프로그램의 태스크 또는 스레드마다 하나씩 존재한다. 고급 프로그래밍 언어에서는 콜 스택의 세부 사항이 프로그래머에게 숨겨져 있지만, 어셈블리 언어에서는 프로그래머가 직접 스택을 조작해야 한다. 콜 스택의 구체적인 동작 방식은 컴파일러, 운영 체제, 명령 집합에 따라 달라진다.

콜 스택에 할당된 공간이 모두 소모되면 스택 오버플로 오류가 발생하며, 이 경우 프로그램이 크래시될 수 있다.

3. 1. 반환 주소 저장

• 각 태스크는 자체 스택을 가지므로 서브루틴은 스레드 안전할 수 있다. 즉, 서로 다른 태스크에서 동시에 같은 서브루틴을 실행할 수 있다.
• 재귀 호출이 자동으로 지원된다. 함수가 자신을 재귀적으로 호출할 때, 각 호출에 대한 반환 주소를 저장해야 하며, 스택 구조는 이를 자동으로 제공한다.

3. 2. 지역 변수 및 매개변수 저장

3. 3. 재귀 호출 지원

3. 4. 중첩 함수 지원 (정적 스코프)

4. 구조

콜 스택은 스택 프레임(또는 활성화 레코드)이라는 단위로 구성된다. 각 스택 프레임은 하나의 서브루틴 호출에 해당하며, 일반적으로 다음과 같은 정보를 포함한다.^[1]

• 루틴에 전달된 인수 (매개변수 값)
• 루틴 호출자에게 다시 반환하는 주소
• 루틴의 지역 변수를 위한 공간

콜 스택에 할당된 영역을 다 사용하면 "스택 오버플로우"라고 불리는 런타임 오류가 발생한다.

하나의 실행 중인 프로그램 (더 정확히는 스레드)에는 하나의 콜 스택이 대응하여 존재한다.

저수준 언어 (어셈블리 언어)에서는 프로그래머가 명시적으로 스택을 조작해야 한다. 반면, 고수준 언어에서는 콜 스택은 투명하다. 즉, 프로그래머는 콜 스택의 존재를 의식하지 않고 호출 계층 구조에 의해 실현되는 상위 개념으로서의 프로그램 로직에만 집중할 수 있다.

각 프로그래밍 언어에서의 스택의 상세 정보는 컴파일러, OS, 명령어 집합 등에 의존한다.

4. 1. 스택 프레임

'''스택 프레임'''(stack frame) 또는 '''활성화 레코드'''(activation record)는 머신 종속적이며 ABI에 종속적인 서브루틴 상태 정보를 담고 있는 데이터 구조이다. 각 스택 프레임은 아직 반환으로 종료되지 않은 서브루틴 호출에 해당한다. 예를 들어, `DrawLine`이라는 서브루틴이 `DrawSquare` 서브루틴에 의해 호출되어 현재 실행 중이라면, 콜 스택의 상단 부분은 인접한 그림과 같이 배치될 수 있다.

콜 스택은 '''스택 프레임'''들로 구성된다. 스택의 맨 위에 있는 스택 프레임은 현재 실행 중인 루틴에 대한 것이며, 프레임 내의 정보 (예: 매개변수 또는 지역 변수)에 어떤 순서로든 접근할 수 있다.^[1]

일반적으로 스택 프레임은 최소한 다음 항목들을 포함한다(푸시 순서대로):

• 루틴에 전달된 인수(매개변수 값)(있는 경우).
• 루틴 호출자에게 다시 반환하는 주소(예: `DrawLine` 스택 프레임에서 `DrawSquare`의 코드 주소).
• 루틴의 지역 변수를 위한 공간(있는 경우).

대부분의 시스템에서 스택 프레임은 호출자가 실행되는 동안 가지고 있던 값, 즉 이전 프레임 포인터 레지스터의 값을 담는 필드를 추가로 가지고 있다. 예를 들어, `DrawLine`의 스택 프레임은 `DrawSquare`가 사용하는 프레임 포인터 값을 저장하는 메모리 위치를 갖게 된다 (위 그림에는 표시되지 않음). 이 값은 서브루틴에 진입할 때 저장된다. 스택 프레임의 알려진 위치에 이러한 필드가 있으면 코드는 현재 실행 중인 루틴의 프레임 아래에 있는 각 프레임에 차례로 접근할 수 있으며, 루틴이 반환하기 직전에 프레임 포인터를 ''호출자''의 프레임으로 쉽게 복원할 수 있다.

어떤 목적을 위해, 서브루틴의 스택 프레임과 이를 호출한 측의 스택 프레임은 겹쳐진다고 간주될 수 있으며, 이 겹침은 호출자가 피호출자에게 매개변수를 전달하는 영역으로 구성된다. 일부 환경에서, 호출자는 각 인수를 스택에 푸시하여 스택 프레임을 확장한 다음 피호출자를 호출한다. 다른 환경에서는 호출자가 호출하는 다른 서브루틴에 제공하는 인수를 보관하기 위해 스택 프레임 상단에 미리 할당된 영역을 갖는다. 이 영역은 때때로 '발신 인수 영역' 또는 '호출 영역'이라고 한다. 이 접근 방식에 따라, 해당 영역의 크기는 컴파일러가 호출된 모든 서브루틴에 필요한 가장 큰 크기로 계산한다.

4. 2. 스택 포인터와 프레임 포인터

콜 스택은 스택 자료구조로 구성되어 있어, 함수 호출 시 반환 주소를 스택에 푸시(push)하고, 함수 종료 시 스택에서 반환 주소를 팝(pop)하여 해당 주소로 복귀한다. 이러한 과정을 통해 함수 호출 및 반환이 순차적으로 이루어지며, 스택이 가득 차면 스택 오버플로 오류가 발생한다.

콜 스택은 스택 프레임(또는 액티베이션 레코드)으로 구성되며, 각 스택 프레임은 아직 종료되지 않은 서브루틴 호출에 대한 정보를 담고 있다. 스택 프레임에는 일반적으로 다음 정보가 포함된다.

• 호출된 함수에 전달된 인수 (매개변수 값)
• 호출한 함수로 돌아갈 반환 주소
• 함수의 지역 변수를 위한 공간

스택 프레임의 맨 위는 현재 실행 중인 함수에 해당하며, 이 프레임 내의 정보(매개변수, 지역 변수 등)에 접근할 수 있다.^[1]

함수 프레임의 크기는 함수마다 다를 수 있으며, 함수 반환 시 스택 포인터(SP)는 프레임 포인터(FP) 값으로 복원된다. 프레임 포인터는 함수 호출 직전의 스택 포인터 값을 가리킨다.^[2] 각 스택 프레임은 바로 아래 프레임의 맨 위를 가리키는 스택 포인터를 포함하며, 스택 포인터는 모든 호출 간에 공유되는 가변 레지스터이다.

대부분의 시스템에서 스택 프레임은 호출자가 실행되는 동안 가지고 있던 값, 즉 이전 프레임 포인터 레지스터의 값을 저장한다. 이를 통해 현재 실행 중인 함수 프레임 아래의 각 프레임에 순차적으로 접근하고, 함수 반환 직전에 프레임 포인터를 호출자의 프레임으로 복원할 수 있다.

콜 스택의 주된 목적은 서브루틴 처리 완료 후 제어를 반환할 위치(반환 주소)를 기억하는 것이다.^[7]

5. 동작 방식

콜 스택은 함수의 호출과 반환을 관리하는 데 사용되는 스택 자료구조이다. 함수 호출 시 해당 함수의 정보(반환 주소, 지역 변수, 매개변수 등)가 콜 스택에 쌓이고(push), 함수가 반환될 때 해당 정보가 스택에서 제거(pop)된다.

함수 호출 시, 콜 스택에는 다음과 같은 정보들이 저장된다.

• 반환 주소: 함수 실행이 완료된 후 돌아갈 위치(주소)이다. 이를 통해 호출한 함수로 제어가 다시 넘어갈 수 있다.
• 지역 변수: 함수 내에서만 사용되는 변수들로, 함수가 반환되면 값이 유지되지 않는다.
• 매개변수: 호출하는 코드에서 함수에게 전달하는 값들이다.
• 둘러싸는 서브루틴 컨텍스트: 파스칼, 에이다와 같은 일부 프로그래밍 언어에서, 중첩 함수가 외부 함수의 변수 및 매개변수에 접근할 수 있도록 하는 정보이다.
• 기타 반환 상태: 권한 수준, 예외 처리 정보, 산술 모드 등 함수 반환 시 복원해야 하는 상태 정보가 포함될 수 있다.

6. 사용 예시

다음은 의사 코드를 사용하여 콜 스택의 동작 방식을 보여주는 예시이다. `DrawSquare` 함수가 호출되면, 각 `DrawLine` 호출마다 반환 주소가 콜 스택에 저장되고, `DrawLine` 함수가 종료될 때마다 저장된 반환 주소를 사용하여 `DrawSquare` 함수의 다음 명령으로 복귀한다.

```

subroutine DrawSquare(Point p1, Point p2, Point p3, Point p4)

{

... 생략 ...

DrawLine(p1, p2);

DrawLine(p2, p3);

DrawLine(p3, p4);

DrawLine(p4, p1);

... 생략 ...

}

```

위 의사 고급 프로그래밍 언어의 코드에서 서브루틴 `DrawSquare` 내의 4곳에서 직선을 그리는 서브루틴 `DrawLine`을 호출한다고 할 때, `DrawLine`은 4곳 중 어디로 돌아가야 하는지를 알아야 한다. 일반적으로 `DrawSquare` 코드 내에서 `DrawLine`을 호출하는 각 위치에서 호출 처리의 다음 명령의 주소 (이것을 리턴 주소라고 부른다)를 콜 스택에 저장함으로써 이를 실현한다.

7. 스택 오버플로

콜 스택은 스택으로 구성되어 있어, 호출 측은 반환 주소를 스택에 ''push''하고, 호출된 서브루틴이 완료되면 반환 주소를 콜 스택에서 ''pop''하여 해당 주소로 제어를 반환한다. 호출된 서브루틴이 또 다른 서브루틴을 호출하는 경우에도, 반환 주소를 콜 스택에 push하고, 프로그램에 기록된 대로 정보를 스택에 쌓거나 빼낸다. 어떤 서브루틴에 관한 정보를 콜 스택에 올리는 것을 '''와인드'''('''winding''', '''감기''')라고 하고, 반대로 그것을 삭제하는 것을 '''언와인드'''('''unwinding''', '''풀기''')라고 부른다.

콜 스택에 할당된 영역을 모두 사용하면 "스택 오버플로"라는 런타임 오류가 발생한다. 스택 오버플로는 프로그램의 비정상 종료를 유발하는 심각한 오류이다. 스택 오버플로가 발생했을 때의 동작은 프로그래밍 언어나 실행 환경에 따라 다르지만, 통상 프로그램의 비정상 종료와 같은 미정의 동작을 일으키며, 회복 불가능한 경우가 많다.

소프트웨어를 정상적으로 동작시키기 위해서는 콜 스택을 올바르게 유지하는 것이 중요하다. 콜 스택의 용량은 데스크톱 운영 체제 환경에서도 기본적으로 (스레드마다) 수 MiB 정도밖에 안 되며, 임베디드 환경에서는 더욱 제한이 심하다. 고수준 언어에서는 평소 콜 스택의 존재를 의식하지 않아도 되기 때문에, 힙이 아닌 스택에 거대한 배열을 확보하여 용량을 모두 사용해 버리고 스택 오버플로를 발생시키는 것과 같은 초보적인 실수를 범하는 경우도 있다.

8. 성능 분석

프로그램의 성능 프로파일링을 위해 정기적으로 콜 스택 샘플을 채취할 수 있다. 특정 서브루틴의 주소가 콜 스택 샘플링 데이터에 자주 나타난다면, 이는 코드 병목 현상일 가능성이 높으므로 성능 문제를 검사해야 한다.^[5]

콜 스택 표본을 무작위로 채취하여 프로그램 성능 최적화에 활용할 수 있다. 콜 스택 상에 자주 나타나는 서브루틴은 빈번하게 호출되거나 1회 실행에 시간이 오래 걸린다고 예상할 수 있으며, 해당 호출 횟수를 줄이거나 1회 실행 시간을 단축하면 큰 효과를 기대할 수 있다.

9. 보안

자유 포인터 또는 배열 쓰기에 대한 검사가 없는 언어(예: C)에서는 코드 실행에 영향을 미치는 제어 흐름 데이터(반환 주소 또는 저장된 프레임 포인터)와 간단한 프로그램 데이터(매개변수 또는 반환 값)가 콜 스택에 혼합되는 것이 보안상 위험하며, 가장 일반적인 유형의 버퍼 오버플로우인 스택 버퍼 오버플로우를 통해 악용될 수 있다.^[6]

이러한 공격 중 하나는 임의의 실행 가능한 코드로 버퍼를 채우고, 이 버퍼 또는 다른 버퍼를 오버플로우하여 일부 반환 주소를 실행 가능한 코드를 직접 가리키는 값으로 덮어쓰는 것이다. 결과적으로 함수가 반환될 때 컴퓨터는 해당 코드를 실행한다. 이러한 종류의 공격은 W^X로 차단할 수 있지만, return-to-libc 공격 또는 리턴 지향 프로그래밍과 같이 W^X 보호가 활성화되어 있어도 유사한 공격이 성공할 수 있다. 배열을 반환 스택과 완전히 별도의 위치에 저장하는 등 다양한 완화책이 제안되었다.^[6]

참조

_[1] 웹사이트 Stack frames https://people.cs.ru[...] 2018-02-16
_[2] 웹사이트 Understanding the Stack http://www.cs.umd.ed[...] 2003-06-22
_[3] 문서 AlternativeMicroprocessorDesign
_[4] 간행물 Call Stack Coverage for GUI Test-Suite Reduction http://www.cs.umd.ed[...]
_[5] 웹사이트 Debugging with GDB: Examining the Stack http://www.chemie.fu[...] 1997-10-17
_[6] 문서 The Forth Programming Language - Why YOU should learn it http://www.hcsw.org/[...]
_[7] 문서 Interstage Application Server/Interstage Web Server チューニングガイド - 7.1.4 スタック https://software.fuj[...]
_[8] 문서 x64 calling convention | Microsoft Learn https://learn.micros[...]
_[9] 문서 "/STACK (Stack allocations) | Microsoft Learn" https://learn.micros[...]
_[10] 문서 Threading Programming Guide - Thread Management | Apple Developer Documentation Archive https://developer.ap[...]
_[11] 간행물 “Call Stack Coverage for GUI Test-Suite Reduction” 2006-11
_[12] 간행물 “Call-Stack Coverage for GUI Test-Suite Reduction” IEEE Press 2008